package com.dyz.leetcode._20_dynamicProgramming._70;

import java.util.Arrays;

public class _70_climbStairs02 {
    //dfs+记忆话搜索
    public int climbStairs(int n) {
        int[] memo = new int[n+1];
        Arrays.fill(memo, -1);
        return dfs(n, memo);
    }

    private int dfs(int n, int[] memo) {
        if(n==1){return 1;}
        if(n==2){return 2;}
        if(memo[n]!=-1){return memo[n];}
        int left = dfs(n-1, memo);
        int right = dfs(n-2, memo);
        memo[n] = left+right;

        return left+right;

    }
}
